SHA-1
Secure Hash Algorithm 1 — алгоритм криптографического хеширования. Описан в RFC 3174. Для входного сообщения произвольной длины (максимум 2^{64}-1 бит) алгоритм генерирует 160-битное хеш-значение, называемое также дайджестом сообщения. Используется во многих криптографических приложениях и протоколах. Также рекомендован в качестве основного для государственных учереждений в США. Принципы, положенные в основу SHA-1, аналогичны тем, которые использовались Рональдом Ривестом при проектировании MD4. История В 1993 году NSA совместно с NIST разработали алгоритм безопасного хеширования (сейчас известный как SHA-0) (опубликован в документе ''FIPS'' PUB 180) для стандарта безопасного хеширования. Однако вскоре NSA отозвало данную версию, сославшись на обнаруженную ими ошибку, которая так и не была раскрыта. И заменило его исправленной версией, опубликованной в 1995 году в документе ''FIPS'' PUB 180-1. Эта версия и считается тем, что называют SHA-1. Много спустя, на конференции CRYPTO в 1998 году два французских исследователя представили атаку на алгоритм SHA-0, которая не работала на алгоритме SHA-1 Возможно, это и была ошибка, открытая NSA. Описание алгоритма SHA-1 реализует однонаправленную хеш-функцию, простроенную на идее функции сжатия. Входами функции сжатия являются блок сообщения длиной 512 бит и выход предыдущего блока сообщения. Выход представляет собой значение всех хеш-блоков до этого момента. Иными словами хеш блока M_i равен h_i = f(M_i, h_{i-1}) . Хеш-значением всего сообщения является выход последнего блока. Инициализация Исходное сообщение разбивается на блоки по 512 бит в каждом. Последний блок дополняется до длины, кратной 512 бит. Сначала добавляется 1 а потом нули, чтобы длина блока стала равной 512 — 64 бит. В оставшиеся 64 бита записывается длина исходного сообщения. Дополнение последнего блока осуществляется всегда, даже если сообщение уже имеет нужную длину. Таким образом, число добавляемых битов находится в диапазоне от 1 до 512. Инициализируются пять 32-битовых переменных. A = a = 0x67452301 B = b = 0xEFCDAB89 C = c = 0x98BADCFE D = d = 0x10325476 E = e = 0xC3D2E1F0 Определяются четыре нелинейные операции и четыре константы. Главный цикл Главный цикл итеративно обрабатывает каждый 512-битный блок. Итерация состоит из четырех этапов по двадцать операций в каждом. Блок сообщения преобразуется из 16 32-битовых слов M_i в 80 32-битовых слов W_j по следующему правилу: W_t = M_t при 0≤t≤15 W_t = ( W_t-3 \oplus W_t-8 \oplus W_t-14 \oplus W_t-16) << 1 при 16≤t≤79 здесь << – это циклический сдвиг влево для t от 0 до 79 temp = (a<<5) + F_t (b,c,d) + e + W_t + K_t e = d d = c c = b<<30 b = a a = temp После этого a, b, c, d, e прибавляются к A, B, C , D , E соответственно. Начинается следующая итерация. Итоговым значением будет объединение пяти 32-битовых слов в одно 160-битное хеш-значение. Псевдокод SHA-1 Псевдокод алгоритма SHA-1 следущий: Замечание: Все используемые переменные 32 бита. Инициализация переменных: h0 = 0x67452301 h1 = 0xEFCDAB89 h2 = 0x98BADCFE h3 = 0x10325476 h4 = 0xC3D2E1F0 Предварительная обработка: Присоединяем бит '1' к сообщению присоединяем k битов '0', где k наименьшее число ≥ 0 такое что длина получившегося сообщения(в битах) сравнима с 448 (mod 512) добавленная длина сообщения в битах, (после предварительной обработки), в битах. В процессе сообщение разбивается последовательно по 512 бит: for перебираем все такие части разбиваем этот кусок на 16 частей, слов по 32-бита wi, 0 <= i <= 15 16 слов по 32-бита расширяются в 80 32-битовых слов: for i from 16 to 79 wi = (wi-3 xor wi-8 xor wi-14 xor wi-16) leftrotate 1 Инициализация хеш-значений этой части: a = h0 b = h1 c = h2 d = h3 e = h4 Основной цикл: for i from 0 to 79 if 0 ≤ i ≤ 19 then f = (b and c) or ((not b) and d) k = 0x5A827999 else if 20 ≤ i ≤ 39 f = b xor c xor d k = 0x6ED9EBA1 else if 40 ≤ i ≤ 59 f = (b and c) or (b and d) or (c and d) k = 0x8F1BBCDC else if 60 ≤ i ≤ 79 f = b xor c xor d k = 0xCA62C1D6 temp = (a leftrotate 5) + f + e + k + wi e = d d = c c = b leftrotate 30 b = a a = temp Добовляем хеш-значение этой части к результату: h0 = h0 + a h1 = h1 + b h2 = h2 + c h3 = h3 + d h4 = h4 + e Итог конечное хеш-значение: digest = hash = h0 append h1 append h2 append h3 append h4 Вместо оригинальной формулировки FIPS PUB 180-1 приведены следующие эквивалентные выражения и могут быть использованы на компьютере f в главном цикле: (0 ≤ i ≤ 19): f = d xor (b and (c xor d)) (альтернатива 1) (0 ≤ i ≤ 19): f = (b and c) xor ((not b) and d) (альтернатива 2) (0 ≤ i ≤ 19): f = (b and c) + ((not b) and d) (альтернатива 3) (40 ≤ i ≤ 59): f = (b and c) or (d and (b or c)) (альтернатива 1) (40 ≤ i ≤ 59): f = (b and c) or (d and (b xor c)) (альтернатива 2) (40 ≤ i ≤ 59): f = (b and c) + (d and (b xor c)) (альтернатива 3) (40 ≤ i ≤ 59): f = (b and c) xor (b and d) xor (c and d) (альтернатива 4) Примеры Ниже приведены примеры хешей SHA-1. Для всех сообщений подразумевается использование кодировки ASCII. Хеш панграммы на русском: SHA-1("В чащах юга жил бы цитрус? Да, но фальшивый экземпляр!") = 9e32295f 8225803b b6d5fdfc c0674616 a4413c1b Хеш панграммы на английском: SHA-1("The quick brown fox jumps over the lazy dog") = 2fd4e1c6 7a2d28fc ed849ee1 bb76e739 1b93eb12 SHA-1("sha") = d8f45903 20e1343a 915b6394 170650a8 f35d6926 Небольшое изменение исходного текста (одна буква в верхнем регистре) приводит к сильному изменению самого хеша. Это происходит вследствие лавинного эффекта. SHA-1("Sha") = ba79baeb 9f10896a 46ae7471 5271b7f5 86e74640 Даже для пустой строки вычисляется нетривиальное хеш-значение. SHA-1("") = da39a3ee 5e6b4b0d 3255bfef 95601890 afd80709 Криптоанализ Криптоанализ хеш-функций направлен на исследование уязвимости к различного вида атакам. Основные из них: * нахождение коллизий — ситуация, когда двум различным исходным сообщениям соответствует одно и то же хеш-значение. * нахождение прообраза — исходного сообщения — по его хешу. При решении методом «грубой силы»: * вторая задача требует 2160 операций. * первая же требует в среднем 2160/2 = 280 операций, если использовать парадокс дней рождения. От устойчивости хеш-функции к нахождению коллизий зависит безопасность электронной цифровой подписи с использованием данного хеш-алгоритма. От устойчивости к нахождению прообраза зависит безопасность хранения хешей паролей для целей аутентификации. В январе 2005 года Rijmen and Oswald опубликовали сообщение об атаке на усеченную версию SHA-1 (53 раунда вместо 80), которая позволяет находить коллизии меньше, чем за 280 операций. В феврале 2005 года Сяоюнь Ван, Йицунь Лиза Йинь и Хунбо Ю представили атаку на полноценный SHA-1, которая требует менее 269 операций. О методе авторы пишут: Мы представляем набор методик и соответствующих технологий, которые могут быть использованы для устранения главных препятствий в нахождении коллизий в SHA-1. Сначала мы ищем близкие к коллизии дифференциальные пути, которые имеют небольшой "вес Хамминга" в "векторе помех", где каждый 1-бит представляет 6-шаговую локальную коллизию. Потом, мы соответствующим образом корректируем дифференциальный путь из первого раунда до другого приемлимого дифференциального пути, чтобы избежать неприемлимых последовательных коллизий и усеченных коллизий. В конце концов мы преобразуем два одноблоковых близких к коллизии дифференциальных пути в один двухблоковый коллизионный путь с удвоенной вычислительной сложностью. Также они заявляют: В особенности, наш анализ основан на оригинальных дифференциальных атаках на SHA-0, близких к коллизиям атаках на SHA-0, мультиблокой методике, а также методике модификации исходного сообщения, использованной при атаке на MD5. Взлом SHA-1 не был бы возможным без этих мощных аналитических методологий. Статья с описанием алгоритма была опубликована в августе 2005 года на конференции CRYPTO. В этой же статье авторы опубликовали атаку на усеченный SHA-1 (58 раундов), которая позволяет находить коллизии за 233 операций. В августе 2005 года на CRYPTO 2005 эти же специалисты представили улучшенную версию атаки на полноценный SHA-1, с вычислительной сложностью в 263 операций. В декабре 2007 года детали этого улучшения были проверены Мартином Кохраном. Кристоф де Каньер и Кристиан Рехберг позже представили усовершенствованную версию атаки на SHA-1, за что были удостоены награды за лучшую статью на конференции ASIACRYPT 2006. Ими была представлена двух-блоковая коллизия на 64-раундовый алгоритм с вычислительной сложностью около 235 операций. Существует масштабный исследовательский проект, стартовавший в технологическом университете австрийского города Грац, который : «… использует компьютеры соединенные через Интернет, для проведения исследований в области криптоанализа. Вы можете поучаствовать в проекте загрузив и запустив бесплатную программу на своем компьютере.» Хотя теоретически SHA-1 считается взломанным (количество вычислительных операций сокращено в 280-63 = 131 000 раз), на практике подобный взлом неосуществим, так как займет пять миллиардов лет. Бурт Калински, глава исследовательского отдела в «лаборатории RSA» предсказывает, что первая атака по нахождению прообраза будет успешно осуществлена в ближайшие 5-10 лет. Ввиду того, что теоретические атаки на SHA-1 оказались успешными NIST планирует полностью отказаться от использования SHA-1 в цифровых подписях. 2 ноября 2007 года NIST анонсировало конкурс по разработке нового алгоритма SHA-3, который продлится до 2012 года. Сравнение SHA-1 с другими алгоритмами Сравнение с MD5 И MD5, и SHA-1 являются, по сути, улучшенными продолжениями MD4. Сходства: # Четыре этапа. # Каждое действие прибавляется к ранее полученному результату. # Размер блока обработки равный 512 бит. # Оба алгоритма выполняют сложение по модулю 232, они рассчитаны на 32-битную архитектуру. Различия: # В SHA-1 на четвертом этапе используется та же функция f, что и на втором этапе. # В MD5 в каждом действии используется уникальная прибавляемая константа. В SHA-1 константы используются повторно для каждой из четырех групп. # В SHA-1 добавлена пятая переменная. # SHA-1 использует циклический код исправления ошибок. # В MD5 четыре сдвига, используемые на каждом этапе отличаются от значений, используемых на предыдущих этапах. В SHA на каждом этапе используется постоянное значение сдвига. # В MD5 четыре различных элементарных логических функции, в SHA-1 — три. # В MD5 длина дайджеста составляет 128 бит, в SHA-1 — 160 бит. # SHA-1 содержит больше раундов (80 вместо 64) и выполняется на 160-битном буфере по сравнению со 128-битным буфером MD5. Таким образом, SHA-1 должен выполняться приблизительно на 25% медленнее, чем MD5 на той же аппаратуре. Брюс Шнайер делает следующий вывод : «SHA-1 — это MD4 с добавлением расширяющего преобразования, дополнительного этапа и улучшенным лавинным эффектом. MD5 — это MD4 с улучшенным битовым хешированием, дополнительным этапом и улучшенным лавинным эффектом.» Сравнение с ГОСТ Р 34.11-94 Ряд отличительных особенностей ГОСТ Р 34.11-94: # При обработке блоков используются преобразования по алгоритму ГОСТ 28147—89; # Обрабатывается блок длиной 256 бит, и выходное значение тоже имеет длину 256 бит. # Применены меры борьбы против поиска коллизий, основанном на неполноте последнего блока. # Обработка блоков происходит по алгоритму шифрования ГОСТ 28147—89, который содержит преобразования на S - боксах, что существенно осложняет применение метода дифференциального криптоанализа к поиску коллизий алгоритма ГОСТ Р 34.11-94. Это существенный плюс по сравнению с SHA-1. # Теоретическая криптостойкость ГОСТ Р 34.11-94 равна 2128, что во много раз превосходит 280для SHA-1. # Скорость обработки данных для SHA-1 - 48.462*220 байт/с, а для ГОСТ Р 34.11-94 - 9.977*220 байт/с. Сравнение с другими SHA В таблице, «промежуточный размер хеша» означает «размер внутренней хеш-суммы» после каждой итерации. Использование Хеш-функции используются в системах контроля целостности программного кода и данных, системах электронной подписи, а также для построения кодов аутентификации. SHA-1 является наиболее распространенным из всего семейства SHA и применяется в различных широко распространенных криптографических приложениях и алгоритмах. SHA-1 используется в следующих приложениях: * S/MIME — дайджесты сообщений. * SSL — дайджесты сообщений. * IPSec — для алгоритма проверки целостности в соединении «точка-точка». * SSH — для проверки целостности переданных данных. * PGP — для создания электронной цифровой подписи. Примечания Ссылки * RFC 3174 * Обзор SHA-1 от Консорциума Всемирной паутины * Взлом SHA-1 * Онлайн Взлом SHA1 * Поиск по базам и восстановление SHA1 * Доклад о взломе SHA1 * Брюс Шнайер о взломе SHA * Последствия удачных атак на SHA-1 * Вычисление SHA1 суммы онлайн Литература * * Категория:Криптографические хеш-функции cs:Secure Hash Algorithm da:SHA de:Secure Hash Algorithm en:SHA hash functions es:SHA fi:SHA fr:SHA-1 he:SHA hr:SHA-1 it:Secure Hash Algorithm ja:SHA ko:SHA lt:SHA nl:SHA-familie pl:SHA-1 pt:SHA1 sk:Secure Hash Algorithm sr:SHA vi:SHA zh:SHA 家族